//给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [1,1,1,2,2,3], k = 2
//输出: [1,2]
// 
//
// 示例 2: 
//
// 
//输入: nums = [1], k = 1
//输出: [1] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// k 的取值范围是 [1, 数组中不相同的元素的个数] 
// 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的 
// 
//
// 
//
// 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。 
//
// Related Topics 数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列） 👍 1759 👎 0

  
package com.tyrone.leetcode.editor.cn;

import java.util.*;
import java.util.stream.Collectors;

public class TopKFrequentElements{
    public static void main(String[] args) {
       Solution solution = new TopKFrequentElements().new Solution();
        int[] ints = solution.topKFrequent(new int[]{1,1,1,2,2,3}, 2);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /**
         * 直接用流排序了
         * @param nums
         * @param k
         * @return
         */
//    public int[] topKFrequent(int[] nums, int k) {
//        Map<Integer,Integer> map = new HashMap<>();
//        for (int num : nums) {
//            map.put(num,map.getOrDefault(num, 0)+1);
//        }
//        int[] array = map.entrySet().stream().sorted(((o1, o2) -> o2.getValue().compareTo(o1.getValue()))).limit(k).mapToInt(Map.Entry::getKey).toArray();
//        return array;
//
//    }

        /**
         * 用小根堆排除掉频率低的
         * @param nums
         * @param k
         * @return
         */
//        public int[] topKFrequent(int[] nums, int k) {
//            Map<Integer,Integer> map = new HashMap<>();
//            for (int num : nums) {
//                map.put(num,map.getOrDefault(num, 0)+1);
//            }
//            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
//                @Override
//                public int compare(Integer o1, Integer o2) {
//                    return map.get(o1)-map.get(o2);
//                }
//            });
//            for (Map.Entry<Integer, Integer> en : map.entrySet()) {
//                if (priorityQueue.size()<k){
//                    priorityQueue.add(en.getKey());
//                }else if((en.getValue() > map.get(priorityQueue.peek()))){
//                    priorityQueue.remove();
//                    priorityQueue.add(en.getKey());
//                }
//            }
//            int arr[] =new int[k];
//            int i =0;
//            while (!priorityQueue.isEmpty()) {
//                arr[i]=priorityQueue.remove();
//                i++;
//            }
//            return arr;
//
//        }
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            ArrayList<Integer>[] lists = new ArrayList[nums.length+1];
            for (Map.Entry<Integer, Integer> en : map.entrySet()) {
                if (lists[en.getValue()] == null) lists[en.getValue()] = new ArrayList();
                lists[en.getValue()].add(en.getKey());
            }
            int [] res = new int[k];
            int m = 0;
            for (int i = lists.length - 1; m != k; i--) {
                if (lists[i] == null) continue;
                for (Integer integer : lists[i]) {
                    res[m++] = integer;
                    if (m==k) return res;
                }
            }
            return res;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}